package 剑指offer;

import java.util.Arrays;

/**
 * @author zhangjunfei
 * @date 2023/8/2 14:05
 */
public class O_40 {

    public int[] getLeastNumbers(int[] arr, int k) {
        qSort(arr, 0, arr.length-1);
        return Arrays.copyOfRange(arr, 0, k-1);
    }


    public static void qSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int index = partion(arr, left, right);
        qSort(arr, left, index);
        qSort(arr, index + 1, right);
    }

    public static int  partion(int[] arr, int left, int right) {
        int privot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= privot) {
                right--;
            }
            arr[left] = arr[right];
            while (left < right && arr[left] <= privot) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = privot;
        return left;
    }
}
